package com.mgq.algorithm.morris;

import com.mgq.algorithm.twotree.TreeNode;

/**
 * Morris遍历 ( 使用空间复杂度为O(1) )
 * Morris遍历细节
 * 假设来到当前节点cur，开始时cur来到头节点位置
 * 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
 * 2)如果cur有左孩子，找到左子树上最右的节点mostRight:
 *  a.如果mostRight的右指针指向空，让其指向cur,然后cur向左移动(cur = cur.left)
 *  b.如果mostRight的右指针指向cur，让其指向null,然后cur向右移动(cur = cur.right)
 * 3) cur为空时遍历停止
 */
public class Morris {
    /**
     * Morris遍历
     * 1,2,4,2,5,1,3,6,3,7
     * @param node
     */
    public static void morriesTraversal(TreeNode node) {
        TreeNode cur=node;
        TreeNode mostRight = null;
        while (cur != null) {
            System.out.println(cur);
            if (cur.left != null) {
                mostRight = cur.left;
                while (mostRight.right != null&&mostRight.right!=cur) {
                    mostRight=mostRight.right;
                }
                //表示mostRight第一次左子树的最右节点
                if (mostRight.right == null) {
                    //让mostRight的右指针指向cur,然后cur向左移动
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                    //此时应该执行 cur = cur.right; 由于这个方法执行完毕后
                    //会执行38行,所以不能重复执行
                }
            }
            cur = cur.right;

        }
    }

    /**
     * pre 先序遍历 使用Morris实现
     * 只访问一次的node: 直接打印 (没有左子树的节点,只访问一次)
     * 访问两次的node:  第一次打印
     * 1,2,4,2,5,1,3,6,3,7
     * @param node
     */
    public static void pre(TreeNode node) {
        TreeNode cur=node;
        TreeNode mostRight = null;
        while (cur != null) {

            if (cur.left != null) { //有左树
                mostRight = cur.left;
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                //表示mostRight第一次左子树的最右节点
                if (mostRight.right == null) {
                    System.out.println(cur);
                    //让mostRight的右指针指向cur,然后cur向左移动
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            } else { //没有左树
                System.out.println(cur);
            }
            cur = cur.right;

        }
    }
    /**
     * mid 中序遍历 使用Morris实现
     * 只访问一次的node: 直接打印 (没有左子树的节点,只访问一次)
     * 访问两次的node:  第二次打印
     * 1,2,4,2,5,1,3,6,3,7
     * @param node
     */
    public static void mid(TreeNode node) {
        TreeNode cur=node;
        TreeNode mostRight = null;
        while (cur != null) {

            if (cur.left != null) { //有左树
                mostRight = cur.left;
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                //表示mostRight第一次左子树的最右节点
                if (mostRight.right == null) {
                    //让mostRight的右指针指向cur,然后cur向左移动
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { //第二次来到这个节点
                    System.out.println(cur);
                    mostRight.right = null;
                }
            } else { //没有左树
                System.out.println(cur);
            }
            cur = cur.right;

        }
    }

    /**
     * post 后序遍历 使用Morris实现
     * 访问两次的node:  第二次逆序打印左树的右边界
     * 最后遍历完成后,打印整棵树的右节点
     *  1,   2,  4,  2,  5,  1,  3,  6,  3,  7
     *  x    x   x   √   x   √   x   x   √   x
     *               4       5,2         6
     *                                     单独逆序打印整棵树的右边界 7,3,1
     * 4,5,2,6,7,3,1
     * @param node
     */
    public static void post(TreeNode node) {
        TreeNode cur=node;
        TreeNode mostRight = null;
        while (cur != null) {
            if (cur.left != null) {
                mostRight = cur.left;
                while (mostRight.right != null&&mostRight.right!=cur) {
                    mostRight=mostRight.right;
                }
                //表示mostRight第一次左子树的最右节点
                if (mostRight.right == null) {
                    //让mostRight的右指针指向cur,然后cur向左移动
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                    //逆序打印左树的右边界
                    printXEdge(cur.left);
                    //此时应该执行 cur = cur.right; 由于这个方法执行完毕后

                }
            }
            cur = cur.right;
        }

        //最后逆序打印整棵树的右边界
        printXEdge(node);
    }

    public static void printXEdge(TreeNode x) {
        TreeNode tail = reverseRight(x);
        TreeNode cur = tail;
        while (cur != null) {
            System.out.println(cur);
            cur = cur.right;
        }
        //最后把链表还原
        reverseRight(tail);
    }
    /**
     * 逆序打印右边界
     * 单链表的反转
     * 1->2->3->4
     * null<-1<-2<-3<-4
     * 4->3->2->1
     * @param cur
     */
    private static TreeNode reverseRight(TreeNode cur) {
        TreeNode pre = null;
        TreeNode next = null;
        while (cur != null) {
            next=cur.right;
            cur.right = pre;
            pre=cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        morriesTraversal(node1);
        System.out.println("---------------先序-----------------");
        pre(node1);
        System.out.println("---------------中序-----------------");
        mid(node1);
        System.out.println("---------------后序-----------------");
        post(node1);

        /*TreeNode treeNode = reverseRight(node1.right);
        System.out.println(treeNode);*/
    }
}
